package leetcode.editor.cn;
//[338]比特位计数
public class CountingBits338{
public static void main(String[] args) {
   Solution solution = new CountingBits338().new Solution();
   
}

  //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n+1];
        res[0] = 0;
        for (int i = 1; i <= n; i++) {
            //方法 1： 	执行耗时:2 ms,击败了41.44% 的Java用户
            //	内存消耗:45.4 MB,击败了78.04% 的Java用户
//            res[i] = getBitCount(i); //正常解法


            //方法 2：	执行耗时:1 ms,击败了99.51% 的Java用户
            //	内存消耗:45.4 MB,击败了91.00% 的Java用户
//            int pre = i & (i - 1);//cache 加速 ，加判断。。是否有 pre.
//            if (res[pre]!=0){
//                res[i] = res[pre]+1;
//            }else {
//                res[i] = getBitCount(i);
//            }


            //方法 3：	执行耗时:1 ms,击败了99.51% 的Java用户
            //	内存消耗:45.3 MB,击败了94.21% 的Java用户
            int pre = i & (i - 1);//cache 加速 .不需要判断，都可以递推。。。。！
            res[i] = res[pre]+1;

        }
        return res;
    }

    public int getBitCount(int n){
        int cout = 0;
        while (n!=0){
            cout++;
            n = n & (n-1);
        }
        return cout;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}